home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-04
/
prolog_2.zip
/
CAD.ZIP
/
ATGS.DOC
next >
Wrap
Text File
|
1987-04-05
|
20KB
|
529 lines
DREXEL ATGS DOCUMENTATION 4/5/87
Preliminary Documentation for
Drexel Automatic Test Generation System
I. Introduction
Drexel ATGS was the result of a course project at Drexel
University involving the design of a digital logic test
generation system for combinational circuits. The system is
currently D-Algorithm based, and is capable of providing a
complete, though not minimal set of tests for any combinational
circuit. New logic elements may be defined by the user. The only
constraint is time and computer memory available. The D-algorithm
is currently used, but in recognition of its deficiencies may in
the future be replaced by PODEM. A branch and bound step may also
be added to attempt to provide a less redundant (though still not
minimal) test set.
Input is in the form of text files. The user of ATGS
provides:
1) A netlist description. This includes all nets in the
circuit and description is in terms of the elements which a net
connects.
2) A gatelist description. The netlist and gatelist
description could be derived from each other, but we have chosen
to require the user to give both.
3) A list of inputs.
4) A list of outputs.
5) A list of input constraints which correspond to providing
double rail inputs.
6) A supplemental description of whatever logic elements are
not included in the standard ATGS library.
ATGS is PROLOG based, and runnable with PD PROLOG, or other
Edinburgh dialect Prologs with minor modification. ATGS is
supplied in the form of a Prolog source file (ATGS.PRO). Circuit
files are also Prolog source files. After loading, the user has a
choice of activities, which include generating tests for
individual gates, all inputs, outputs, or fanout points. The
test results can be written out to a file with ADA Prolog
versions FS and higher.
A sample source file provided is a circuit provided by Mark
Karpovsky of Boston University, and is entitled "samcir.pro".
1
DREXEL ATGS DOCUMENTATION 4/5/87
II. Writing circuit files for ATGS
A circuit file is a Prolog language source file. If A.D.A.
Prolog is being used, the extension (character string after the
"." ) must be ".pro".
Let us consider the small example file simcir.pro, which
contains three two input and gates. The schematic representation
of this file is:
gate "o1:"
_ gate "p1:"
n1--->| | n5 _
|&|--.----------->| | n6
n2--->|_| | |&|--------> (output1)
| /------>|_|
n3---------|---/ _
\----------->| | n7
gate "p2": |&|--------> (output2)
n4--------------------->|_|
The corresponding ciruit file must contain the following
elements:
1) A list of inputs: inputs( [n1,n2,n3,n4] ).
2) A list of outputs: outputs( [n6,n7] ).
3) A list of logic elements: elements( [o1,p1,p2] ).
4) An individual descriptor for each logic element:
o1( and2, 2, [n1,n2], n5 ).
p1( and2, 2, [n3,n5], n6 ).
p2( and2, 2, [n4,n5], n7 ).
5) An individual netlist descriptor for each net:
n1( 1, x1, [o1] ).
n2( 2, x2, [o1] ).
n3( 3, x3, [p1] ).
n4( 4, x4, [p2] ).
n5( 5, o1, [p1,p2] ).
n6( 6, p1, [f1] ).
n7( 7, p2, [f2] ).
The names by which you refer to the logic elements and nets are
arbitrary. Each logic descriptor has the following fields:
a) The gate type ("and2", "or3", ...)
b) The second field, which is a number, is not actually used
2
DREXEL ATGS DOCUMENTATION 4/5/87
by the current algorithm.
c) A Prolog list: [<net1>, <net2>,...] of all the elements
which serve as inputs to that logic element. The order in
they are given is important. When you specify a test of the
nth gate input gate input, you are actually testing the gate
input which is connected to the nth net in the list,
starting with 1 and counting from the left.
You can also add input constraints to the system. For example,
n4 might not be an externally accessible to the system, but the
internally generated complement of n1. We could modify the above
description to reflect this in the following way:
1) Remove "n4" from the list of inputs.
2) Add the following statement in the circuit file:
in1( constraint1, 1, [n1], n4 ).
The term "constraint1" refers to an inverter constraint,
and is defined in DREXATGS itself.
3) Add the element "in1" to the list of circut elements:
elements( [o1,p1,p2,in1] ).
The purpose of a constraint is to force some set of inputs to
behave in a particular fashion while not actually generating
tests for the constraint itself.
III. Questions to ask ATGS
ATGS considers only single stuck-at faults. That is, it
generates tests which detect variation in circuit behavior as a
result of some gate input being stuck at a either stuck-at-0 or
stuck-at-1, which we abbreviate sa0 and sa1.
You can test the output of any gate in the circuit with the
following question:
gentestoutp( <gate name>, <fault>, <InVector>, <OutVector> ).
Here <gate name> is o1, p1, and p2, <fault> is sa0 or sa1. You
can name <InVector> according to the rules which govern Prolog
variables. It must begin with a capital, and be an alphanumeric
string. The same for <OutVector>, since it is through these
variables that the Prolog system will return the input set and
ouput set which indicate the absence of the tested-for fault.
For example, if we give the goal:
gentestoutp( o1, sa0, In, Out ).
3
DREXEL ATGS DOCUMENTATION 4/5/87
we get:
In = [n4(1),n2(1),n1(1)]
Out = [n7(d)].
The meaning of the input test set should be quite obvious: we set
these inputs to test the circuit. Doubtless you are wondering:
What is the meaning of n7(d), where "d" is not thee expected
Boolean value? The "d" is d-algorithm's way of saying that this
output will be 1 in a correctly functioning circuit, and 0 in a
circuit which has the tested for fault. Always, there is this
equivalence:
"d" ---> { 1 --> correct functioning, 0 --> fault }
"db"---> { 0 --> correct functioning, 1 --> fault }
It is also possible to test for input stuck-at-faults, with
the goal:
gentestinp( <gate name>, <input number>,
<fault>, <InVector>, <OutVector> ).
There is one new parameter, the input number. Recall that a gate
description has a list of inputs. Each input has a number,
starting from the left and beginning with one, that corresponds
to the input number. So if we wished to test the input of gate
"p2" which is connected to net "n4", we would refer to the gate
description:
p2( and2, 2, [n4,n5], n7 ).
and observe that "n4" is the first input in the list, and thus
connected to input number 1. So to test for a sa0 fault at this
point we would give the following goal:
gentestinp( p2, 1, sa0, In, Out ).
Suppose we wish to save the tests for further processing.
Then there are two related goals which facilitate this:
ftinp( <gate>, <input>, <fault> )
ftout( <gate>, <fault> )
These goals save the test in memory as a Prolog clause, and print
the results to the screen as well. Hence it is not necessary to
give variable names for the returned results, and there are two
fewer arguments.
If you are using types FS or higher A.D.A. Prolog, it is
possible to write out the clauses into a disk database. Use the
following invocation:
4
DREXEL ATGS DOCUMENTATION 4/5/87
update( user, <testfile> ).
where <testfile> is a convenient file name. Give only the part of
the filename before the dot - the system will automatically
append ".pro" to it.
You can also erase the accumulated tests if you wish with
the invocation:
forget( user )
IV. Generating a Complete Set of Tests for a Circuit.
A complete set of tests is defined as one which will detect
any single stuck-at-fault anywhere in the circuit. There is no
guarentee that multiple stuck-at-faults can be detected, since
one can mask another. The test set generated by ATGS is not
minimal. In real life, it is seldom possible to generate a
minimal test set, or it may require expenditure of computing
power incommensurate with the reduction of testing cost.
There are three goals in the system which in combination
will generate a complete test. There is a theorem which states
that if all inputs, outputs, and fanout points of a circuit are
tested for stuck-at-faults,, then the test generated will detect
a single stuck-at-fault anywhere in the circuit. A fanout point
is simply a net which inputs to more than one gate, and we test
for the driver of that net, which is th output of some gate. In
the sample ciruit, there is one net with fanout: n5.
The complete set of goals is:
testinputs.
testoutputs.
testfanouts.
ATGS automatically compiles a list of fanout points, and
obtains the input and output lists from the circuit file, while
ignoring the constraints.
For large circuits you will notice that runtime is
unpredictable, but tending to be largest for gates the furthest
away from the outputs. You may notice that ATGS does not appear
to terminate for some tests, which simply indicates that the
runtime excessive. These are flaws inherent in the D-algorithm.
This field is a deep one, and there are algorithms which claim to
be at least as good ad D-algorithm for all classes of circuits.
If the algorithm appears to be incapable of finding a test
in a reasonable time, it is suggested that you look at the
schematic and decide what an equivalent test might be that is
closer to the outputs. This is case for "samcir.pro". For some
5
DREXEL ATGS DOCUMENTATION 4/5/87
reason, the runtime became prohibitive in finding the following
goal:
gentestoutp( o2, sa1, In, Out ).
It was found that by manually intervening, it was possible to
give the subtitute goal:
gentestinp( p2, 2, sa1, In, Out ),
(input of gate p2 from o2).
which returned a test.
IV. The Gate Library
The kinds of gates which DREXATGS knows about are:
constrainlist( [constraint1] ).
inverter contraints:
constraint1( pc_inv, pdcfinv, pcinv ).
noninverting buffers:
buf( pc_buf, pdcfbuf, pcbuf ).
two input and gates:
and2( pc_and2, pdcfand2, pcand2 ).
three input and gates:
and3( pc_and3, pdcfand3, pcand3 ).
two input or gates:
or2( pc_or2, pdcfor2, pcor2 ).
three input or gates:
or3( pc_or3, pdcfor3, pcor3 ).
The cubic algebra used by D-algorithm requires us to define three
"cubes", or specialized truth tables, for each gate type:
1. The primitive cubes, which are simply the truth tables of
normally operating gates:
pc_inv( 0, [[1]] ).
pc_inv( 1, [[0]] ).
pc_buf( 0, [[0]] ).
pc_buf( 1, [[1]] ).
pc_and2( 0, [[0,_],[_,0]] ).
pc_and2( 1, [[1,1]] ).
pc_and3( 0, [[0,_,_],[_,0,_],[_,_,0]] ).
pc_and3( 1, [[1,1,1]] ).
6
DREXEL ATGS DOCUMENTATION 4/5/87
pc_or2( 1, [[1,_],[_,1]] ).
pc_or2( 0, [[0,0]] ).
pc_or3( 1, [[1,_,_],[_,1,_],[_,_,1]] ).
pc_or3( 0, [[0,0,0]] ).
2. The primitive D-cubes of the logic elements, which describe
the altered logic of a gate with a stuck-at input. Consider the
first statement for an inverter. This says if an inverter has an
input stuck at 0 (sa0(_)), then if you fix the input at 1
([[1]]) the output would be 0 in a normal circuit (db) and 1 in a
faulty circuit. The other entries have the following set of
arguments:
a) Type of fault, and what input where "_" means any input
of the gate.
b) The relation of the output to the fault, where "d" means
normally 1 and "db" means normally 0
c) The input set which is required to produce faulty output,
enclosed in double brackets.
pdcfinv( sa0(_), db, [[1]] ).
pdcfinv( sa1(_), d, [[0]] ).
pdcfbuf( sa0(_), d, [[1]] ).
pdcfbuf( sa1(_), db, [[0]] ).
pdcfand2( sa0(_), d, [[1,1]] ).
pdcfand2( sa1(1), db, [[0,1]] ).
pdcfand2( sa1(2), db, [[1,0]] ).
pdcfand3( sa0(_), d, [[1,1,1]] ).
pdcfand3( sa1(1), db, [[0,1,1]] ).
pdcfand3( sa1(2), db, [[1,0,1]] ).
pdcfand3( sa1(3), db, [[1,1,0]] ).
pdcfor2( sa0(1), d, [[1,0]] ).
pdcfor2( sa0(2), d, [[0,1]] ).
pdcfor2( sa1(_), db, [[0,0]] ).
pdcfor3( sa0(1), d, [[1,0,0]] ).
pdcfor3( sa0(2), d, [[0,1,0]] ).
pdcfor3( sa0(3), d, [[0,0,1]] ).
pdcfor3( sa1(_), db, [[0,0,0]] ).
3) The propagation D-cubes of the elements. The essence of D-
algorithm is to cause a fault to matter at the gate under test,
and propagate it to the outputs so that it becomes observable. To
do this, we must define how a gate transmit faults presented at
its inputs.
/* The propagation D-cubes of the logic elements: */
7
DREXEL ATGS DOCUMENTATION 4/5/87
pcinv( d, [[db]] ).
pcinv( db, [[d]] ).
pcbuf( d, [[d]] ).
pcbuf( db, [[db]] ).
pcand2( d, [[1,d],[d,1],[d,d]] ).
pcand2( db,[[1,db],[db,1],[db,db]] ).
pcor2( d, [[0,d],[d,0,],[d,d]] ).
pcor2( db, [[0,db],[db,0],[db,db]] ).
pcand3( d, [[d,1,1],[1,d,1],[1,1,d],
[d,d,1],[d,1,d],[1,d,d],[d,d,d]] ).
pcand3( db, [[db,1,1],[1,db,1],[1,1,db],[db,db,1],
[db,1,db],[1,db,db],[db,db,db]] ).
pcor3( d, [[d,0,0],[0,d,0],[0,0,d],
[d,d,0],[d,0,d],[0,d,d],[d,d,d]] ).
pcor3( db, [[db,0,0],[0,db,0],[0,0,db],
[db,db,0],[db,0,db],[0,db,db],[db,db,db]] ).
From these examples, you should be able to construct the three
cubic types (primitive, D, and propagation) for any logic
subblocks you wish to include in a circuit. For more information
on D-algorithm I refer you to the excellent, though somewhat
dated book by Brewer and Friedman, Diagnosis & Reliable Design of
Digital Systems, 1976, by the Computer Science Press of
Rockville, MD.
Bob Morein
8
